package com.javaDemo.ti;

import java.util.Arrays;

/**
 * @ClassName: Dizengzixulie
 * @Auther: csy https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/
 * @Date: 2021/6/23 17:18
 * @Description:
 */
public class Dizengzixulie {
    // Dynamic programming.
    public static void main(String[] args) {
        int[] a={10,9,2,5,3,7,101,18};
        int b=lengthOfLIS(a);
        System.out.println(b);
    }
        public static int lengthOfLIS(int[] nums) {
            if(nums.length == 0) {
                return 0;
            }
            int[] dp = new int[nums.length];
            int res = 0;
            Arrays.fill(dp, 1);
            for(int i = 0; i < nums.length; i++) {
                for(int j = 0; j < i; j++) {
                    if(nums[j] < nums[i]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
                res = Math.max(res, dp[i]);
            }
            return res;
        }

}
